\documentclass[a4paper,12pt,oneside]{article}

\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}


%opening
\title{Проект Yoxel}
\author{А. С. Мордвинцев}

\begin{document}
\sloppy  % предпочитать растяжение пробелов заползанию текста на поля

\maketitle

\begin{abstract}
TODO
\end{abstract}

\tableofcontents

\section{Введение}

Целью данного проекта является исследование возможности эффективного применения воксельной графики в интерактивных приложениях.
Для этого предполагается разработать демонстрационное приложение, позволяющее пользователю перемещаться по как можно более реалистичному трехмерному окружению и взаимодействовать с ним. В дальнейшем, наработки, полученные в ходе создания данного прототипа можно использовать при построении полноценного графического движка.

Для достижения качества изображения, сопоставимого с наблюдаемым в современных играх и симуляторах, необходимы значительные вычислительные ресурсы. В качестве вычислительных ускорителей предполагается использование различных доступных на сегодняшний момент архитектур, таких как графические ускорители (поддерживающие технологию CUDA) и процессор Cell BE. Так же интерес представляет разрабатываемая компанией Intel платформа Larrabee, выход которой ожидается в 2009 году. Каждая из этих архитектур обладает своими характерными особенностями, которые могут повлиять на выбор алгоритмов и структур данных, используемых при реализации метода на соответствующей платформе.

В следующих разделах данной главы будет дан краткий обзор истории интерактивной 3D-графики, а так же некоторые соображения относительно ее дальнейшего развития, большое значение в котором будут иметь набирающие популярность высокопроизводительные графические ускорители.

В главе \ref{c:voxel_alg} будут изложены подходы к различным этапам формирования изображения, от генерации и представления сцены в памяти и на дисках, до финальной обработки экранного изображения. Часто, будет предложено несколько вариантов решения одной и той же задачи, так как окончательный выбор может зависеть от конкретной вычислительной архитектуры и требований к программе.

В главе \ref{c:impl} будут описаны детали реализации описанных методов на различных архитектурах, а так же приведены полученные результаты по производительности и требованиям к ресурсам.

Многие из изложенных здесь идей позаимствованы из выступления Next Generation Parallelism in Games by Jon Olick, id Software\footnote{http://s08.idav.ucdavis.edu/} на Siggraph'2008. Толчком к началу работы послужило интервью Джона Кармака\footnote{http://www.pcper.com/article.php?aid=532}.


\subsection{Краткая история интерактивной 3D-графики}

\subsection{Новые вычислительные платформы и их использование в графике}


\section{Обзор алгоритмов воксельной графики}
\label{c:voxel_alg}

Формирование реалистичного трехмерного изображения в реальном времени является сложной задачей, решение которой состоит из множества этапов, про каждый из которых написано немало статей и книг. Рассмотрим для примера некий абстрактный полигональный игровой движок. Для начала трехмерную сцену, которую он будет рисовать, нужно создать. Для этого могут использоваться или специальные редакторы, или трехмерные редакторы общего назначения, такие как Maya или 3ds Max. Сразу заметим, что геометрическую информацию эти программы хранят или в виде наборов полигонов или поверхностей более высокого порядка. На полученные модели накладываются текстуры, предварительно подготовленные в растровых графических редакторах. Затем по полученной геометрии строятся специальные структуры данных, используемые 3D-движком для ускорения рендеринга и и других операций со сценой и объектами в ней (BSP-деревья, октарные деревья и т.д.). Помимо этого, пишутся шейдеры, реализующие требуемую модель освещения, специфические материалы (вода, процедурные текстуры...) и прочие эффекты (bump-mapping, parallax mapping, relief mapping и другие).

После окончания этапа подготовки данных начинается работа самого движка. Он распаковывает и загружает в память данные сцены, компилирует шейдеры и передает в память видеокарты требуемые текстуры. Для взаимодействия с видеокартой используется одно из популярных API 3D графики. На данный момент это Direct3D или OpenGL. 

За инициализацией начинается самая ответственная часть. Нужно по загруженным данным и информации о положении наблюдателя, объектов и источников света строить на экране красивое изображение, причем делать это не более чем за 1/30 секунды. В современных графический движках применяются различные продвинутые алгоритмы преобразования геометрии, отсечения невидимых частей сцены, затенения полигонов, построения теней и т.д. Основными операциями, встречающимися практически на всех этапах построения изображения, являются преобразование координат вершин, выполняемое в вершинном шейдере и растеризация треугольных примитивов с последующей передачей информации об отдельных фрагментах фрагментному шейдеру.

При переходе от полигональной графики к воксельной нужно найти адекватную замену используемым методам на каждом из изложенных выше этапов. Требуется создание новых инструментов для редактирования сцены и новых способов ее визуализации. Различным идеям решения возникающих на разных этапах генерации воксельных сцен и их рендеринга и посвящена эта глава.

\subsection{Представление сцены}

\subsubsection{Трехмерноый массив}
Основная идея воксельной графики заключается в представлении сцены ввиде трехмерного массива кубических ячеек, стороны которых выровнены по осям координат. Таким образом, воксельную сцену можно рассматривать трехмерный аналог двухмерного растрового изображения. Одной из наиболее распространенных областей применения такого представления трехмерных данных является томография. Результатом сканирования является трехмерноый массив, каждый элемент которого содержит численное значение, обозначающее какую-нибудь характеристику одной из ячеек исследуемого объема. В зависимости от типа сканера это может быть плотность, прозрачность для определенного вида излучения, содержание некоторого вещества и т.д. 

Для трехмерной визуализации таких данных применяются различные методы volume rendering. Например, построение полигональных изоповерхностей, соответстующих определенному значению данных сканирования с последующей растеризацией полученныз полигонов. Так как современные графические ускорители хорошо справляются с растеризацией большого количества полигональных примитивов, производительность, достигаемая при использовании такого метода визуализации оказывается достаточной для интерактивных приложений. 

Другие методы реализуют так называемый Direct Volume Rendering, 

Представление сцены в виде трехмерного массива, упомянуть данные MRI.

Кратко про RLE.

Октарные деревья, sparse voxel octree. Хранить/не хранить ссылки на родительские и соседние узлы. Бесконечная рекурсия.

Что хранить в узлах.

Страничная организация памяти, подгрузка данных.

Сжатие данных.

\subsection{Построение сцены}

Растеризация полигональных моделей.

Использование карт высот.

Процедурные методы. Фракталы. Бесконечно детальные поверхности.

Изменение существующих объемных тел в реальном времени.

\subsection{Трассировка лучей}

Рекурсивная и не рекурсивная (со ссылками на соседей и без). Ограничение по глубине.

\subsection{Затенение (Shading)}

Аналогия с фрагментными шейдерами.

Построение теней трассировкой лучей. Отражение и преломление лучей.

Image-space извлечение нормалей.

Кратко про известные image-space техники (ambient occlusion).

Размытие по уровню детализации для сокрытия артефактов.

\subsection{Интеграция с полигональной графикой}

Совместный рендеринг полигональных и воксельных объектов.

Использование растеризации для ускорения рендеринга лучей и проверки видимости объектов.

\section{Реализация}
\label{c:impl}

\subsection{CPU}

\subsection{CUDA}

\subsection{Cell}

\section{Выводы и перспективы}

\end{document}
